
class Link:
    #将Node转入内部封装
    class Node:
        def __init__(self,data):
            self.data = data
            self.next = None

    def __init__(self,data):
        """链表初始化"""
        n = self.Node(data)
        self.head = n
    
    def append(self,data):
        """链表尾插"""
        h = self.head
        n = self.Node(data)
        while h.next:
            h = h.next
        h.next = n

    def happend(self,data):
        """链表头插"""
        h = self.head
        n = self.Node(data)
        self.head = n
        n.next = h

    def printf(self):
        """链表遍历输出"""
        h = self.head
        # end作用是输出类似'2-->6-->5-->1'的效果
        print(h.data,end='')
        while h.next:
            h = h.next
            print('-->',end='')
            print(h.data,end='')

    def inster(self,index,data):
        """链表下标插入"""
        if index < 0:
            print('index out range')
            return
        if index == 0:
            self.happend(data)
            return 
        h = self.head
        n = self.Node(data)
        i = 0
        while h.next and i < index-1:
            h = h.next
            i += 1
        if h.next:
            tem = h.next
            h.next = n
            n.next = tem
        else:
            print('index out range')
    
    def remove(self,index):
        """链表下标删除"""
        if index < 0:
            print('index out range')
            return
        if index == 0:
            h = self.head
            self.head = self.head.next
            h.next = None
            return
        h = self.head
        i = 0
        while h.next and i < index-1:
            h = h.next
            i += 1
        if h.next:
            t = h.next
            h.next = h.next.next
            t.next = None
            
        else:
            print('index out range')
        
    def revered(self):
        """链表翻转"""
        q = None
        h = self.head
        while h:
            t = h.next
            h.next = q
            q = h
            h = t
        self.head = q
    
    def diguirevered(self,h):
        """链表递归翻转"""
        if h is None or h.next is None:
            return h
        nh = self.diguirevered(h.next)
        h.next.next = h
        h.next = None
        return nh



if __name__ == '__main__':
    link = Link(4)
    link.append(6)
    link.append(1)
    link.happend(3)
    link.append(7)
    link.inster(0,5)
    link.printf()
    print()
    # 递归翻转
    a = link.diguirevered(link.head)
    link.head = a
    link.printf()
